package concurrent.sort;

import org.junit.Test;

import java.security.Policy;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class ShellSort {

    static int[] arr = {1,2,3,41,54,12,4,7};

    private String display(int[] arr) {
        String s = "";
        for (int a:arr) {
            s += a + ",";
        }
        return s;
    }

    /**
     * 插入排序
     */
    @Test
    public void insertSort() {
        System.out.println("排序前： " + display(arr));
        int length = arr.length;
        int j, i, key;
        for (i=0; i<length; i++) {
            key = arr[i];
            j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
        System.out.println("排序后： " + display(arr));
    }


    /**
     * 将整个数组根据间隔h分割为若干个子数组
     *          for example h=3 arr[0]、 arr[3]、 arr[6] ... 为一组, arr[1]、 arr[4]、 arr[7] ...为一组，
     * 每次排序时， 分别对每个子数组进行排序
     * 每次排序时，总是交换间隔为h的两个元素
     * 每次排序完成后，可以递减h的值，进行下一次更加精细的排序。直到h为1， 此时等价与一次插入排序
     * 优点：
     *      即使是一个很小的元素在数组的末尾， 由于每次移动都已h为间隔进行，因此数组末尾的小元素可以在
     *      很少次交换次数下，就被置换到最接近元素最终位置的地方
     */
    @Test
    public void shellSort() {
        System.out.println("排序前： " + display(arr));
        // 计算出最大的h值
        int h = 1;
        while (h <= arr.length/3) {
            h = h*3 + 1;
        }
        while (h > 0) {
            for (int i = h; i<arr.length; i++) {
                if (arr[i] < arr[i-h]) {
                    int temp = arr[i];
                    int j = i - h;
                    while (j>=0 && arr[j] > temp) {
                        arr[j + h] = arr[j];
                        j-=h;
                    }
                    arr[j + h] = temp;
                }
            }
            h = (h-1) / 3;
        }
        System.out.println("排序后： " + display(arr));
    }

    public static class ShellSortTask implements Runnable {

        int i = 0, h=0;
        CountDownLatch l;

        public ShellSortTask(int i, int h, CountDownLatch l) {
            this.i = i;
            this.h = h;
            this.l = l;
        }

        @Override
        public void run() {
            if (arr[i] < arr[i-h]) {
                int tmp = arr[i];
                int j = i-h;
                while (j >=0 && arr[j] > tmp) {
                    arr[j + h] = arr[j];
                    j-=h;
                }
                arr[j + h] = tmp;
            }
            l.countDown();
        }
    }

    ExecutorService pool = Executors.newCachedThreadPool();

    public void pShellSort() throws InterruptedException {
        int h = 1;
        CountDownLatch count = null;
        while (h <= arr.length /3) {
            h = h * 3+1;
        }
        while (h>0) {
            if (h >= 4) {
                count = new CountDownLatch(arr.length -h);
            }
            for (int i = h; i<arr.length; i++) {
                if (h>=4) {
                    pool.execute(new ShellSortTask(i, h, count));
                } else {
                    if (arr[i] < arr[i - h]) {
                        int temp = arr[i];
                        int j = i - h;
                        while (j >= 0 && arr[j] > temp) {
                            arr[j + h] = arr[j];
                            j-=h;
                        }
                        arr[j+h] = temp;
                    }
                }
                count.await();
                h = (h-1)/3;
            }
        }
    }

}
